package com.cty.eigthteenthDay;


import java.util.ArrayList;
import java.util.List;

/*
 *给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 * */
public class Q_24 {
    public static void main(String[] args) {

    }

    // 力扣官方题解 方法一:将值复制到数组中后用双指针法
    /*
     * 思路:
     *   将链表的值 遍历存入一个数组中 然后用双指针 从数组的两端往中间遍历
     *   时间复杂度O(n) 空间复杂度O(n)
     * */
    public static boolean isPalindrome(ListNode head) {
        List<ListNode> nodeArrayList = new ArrayList<>();
        ListNode currentNode = head;
        nodeArrayList.add(currentNode);
        while (currentNode.next != null) {
            currentNode = currentNode.next;
            nodeArrayList.add(currentNode);
        }
        int front = 0, back = nodeArrayList.size() - 1;
        while (front < back) {
            if (nodeArrayList.get(front).val != nodeArrayList.get(back).val) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }

    // 力扣官方题解  方法二:递归
    /*
     * 思路:
     *   用一个指针 从前往后遍历 递归到最后一个节点 与前面的节点相比较 如果相等返回true 不相等返回 false
     *   时间复杂度O(n) 空间复杂度O(n) 由于递归要用到栈 所以 时间复杂度是O(n) 用到了栈 效率不高
     * */

    private static ListNode frontPoint;

    public static boolean isPalindrome2(ListNode head) {
        frontPoint = head;
        return recursiveCheck(head);
    }

    // 递归的逻辑
    private static boolean recursiveCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursiveCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPoint.val) {
                return false;
            }
            frontPoint = frontPoint.next;
        }
        return true;
    }

    // 力扣官方题解 方法三: 快慢指针
    /*
     * 思路: 反转后半部分链表 与前半部分进行比对
     * 比对完之后 将链表恢复原样
     *
     * 时间复杂度O(n) 空间复杂度O(1)
     * */
    public static boolean isPalindrome3(ListNode head) {
        if (head == null) return true;
        // 找到前半部分的尾节点并反转后半部分
        ListNode firstPartEnd = findFirstPartEnd(head);
        ListNode reserve = reserve(firstPartEnd.next);
        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = reserve;
        boolean ans = true;
        while (ans && p2 != null) {
            if (p1.val != p2.val) {
                ans = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 将链表反转回来 注意: 从头到尾 firstPartEnd -> firstPartEnd.next 这条链都没有断 反转的只是后面部分的链表
        reserve(reserve);
        return ans;
    }

    // 反转链表的算法
    private static ListNode reserve(ListNode head) {
        ListNode pre = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }

    // 找到牵绊部分链表的尾部
    private static ListNode findFirstPartEnd(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
